"""
问题描述：

题目描述：农夫需要把狼、羊、菜和自己运到河对岸去，
只有农夫能够划船，而且船比较小，除农夫之外每次只能运一种东西，
还有一个棘手问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。
请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。
"""

import sys


def can_cross(state, act):
    """检查当前状态下，是否可以进行渡河操作
       可以渡河的条件：渡河后无农夫一边，羊会偷吃菜，狼会吃羊。
    """
    result = True
    if act[0]!=state[0]: # 农夫不在同一边，失败
        result = False
    new_state = state[:]
    if act[0] == 1:  # 从此岸到对岸
        for i in range(1, 4):
            new_state[i] = state[i] - act[i]
            new_state[i+4] = state[i+4] + act[i]
        new_state[0] = 0
        new_state[4] = 1
    else:
        for i in range(1, 4):
            new_state[i] = state[i] + act[i]
            new_state[i+4] = state[i+4] - act[i]
        new_state[0] = 1
        new_state[4] = 0
    for i in range(8):
        if new_state[i] < 0:
            result = False
    if new_state[0]==0:
        if new_state[1] == 1 and new_state[2] ==1 :
            result = False
        if new_state[2] == 1 and new_state[3] == 1:
            result = False
    else:
        if new_state[5] == 1 and new_state[6] ==1 :
            result = False
        if new_state[6] == 1 and new_state[7] == 1:
            result = False

    return result


def do_cross(state, act):
    """执行渡河操作
       返回操作后的状态
    """
    new_state = state[:]
    if act[0] == 1:  # 从此岸到对岸
        for i in range(1, 4):
            new_state[i] = state[i] - act[i]
            new_state[i+4] = state[i+4] + act[i]
        new_state[0] = 0
        new_state[4] = 1
    else:
        for i in range(1, 4):
            new_state[i] = state[i] + act[i]
            new_state[i+4] = state[i+4] - act[i]
        new_state[0] = 1
        new_state[4] = 0
    return new_state


def cross(state_list):
    """用递归法完成深度搜索"""
    global plancount
    cur_state = state_list[-1][:] # 当前状态
    for act in crossway:
        if can_cross(cur_state, act):
            new_state = do_cross(cur_state, act)
            if new_state not in check_list:
                # 新的状态不能是以前出现过的
                # 加入新的状态
                check_list.append(new_state)
                state_list.append(new_state)
                act_list.append(act[:])
                # 检查是否达到最终状态
                if new_state == [0, 0, 0, 0, 1, 1, 1, 1]:
                    plancount += 1
                    print("\n第{:d}方案, 共{:d}步".format(plancount, len(act_list)))
                    print("状态[农夫，狼，羊，菜，农夫，狼，羊，菜]    渡河动作")
                    for i in range(len(act_list)):
                        print(state_list[i], end="")
                        if act_list[i][0]==1:
                            print("                    ->  ", end="")
                        else:
                            print("                    <-  ", end="")
                        if act_list[i][1] == 1:
                            print("狼 ", end="")
                        if act_list[i][2] == 1:
                            print("羊 ", end="")
                        if act_list[i][3] == 1:
                            print("菜 ", end="")
                        print()
                    print(state_list[-1])
                else:
                    cross(state_list)

                # 恢复状态
                check_list.pop()
                state_list.pop()
                act_list.pop()


if __name__ == '__main__':
    state_list = [] # 状态变化列表，保存从[1, 1, 1, 1, 0, 0, 0, 0]到[0, 0, 0, 0, 1, 1, 1, 1]的过程
                     # 状态分别表示船的位置此岸农夫，狼，羊，菜，对岸农夫，狼，羊，菜
    state_list.append([1, 1, 1, 1, 0, 0, 0, 0])
    act_list = [] # 动作列表（农夫，狼，羊，菜） 农夫1表示从此岸到对岸，0表示从对岸来到此岸
    check_list = [] # 检查状态列表，保存已经出现的状态，以防止出现状态循环
    check_list.append([1, 1, 1, 1, 0, 0, 0, 0])
    crossway = [(1, 0, 0, 0),
                (1, 1, 0, 0),
                (1, 0, 1, 0),
                (1, 0, 0, 1),
                (0, 0, 0, 0),
                (0, 1, 0, 0),
                (0, 0, 1, 0),
                (0, 0, 0, 1)]
    plancount = 0 # 方案数
    cross(state_list)
